A tailored two-phase constructive heuristic for the three-dimensional Multiple Bin Size Bin Packing Problem with transportation constraints

摘要

This paper considers the three-dimensional Multiple Bin Size Bin Packing Problem whichconsists in packing a set of cuboid boxes into containers of various shapes with minimisingunused space. The problem is extended to air cargo where bins are Unit Load Devices,especially designed for fitting in aircraft. We developed a fast constructive heuristic able tomanage the different constraints met in transportation. The heuristic is split into two distinctphases. The first phase deals with the packing of boxes into identical bins using an extensionof the Extreme Points. During this phase, the fragility, stability and orientations of the boxesare taken into account as well as the special shape of the bins and their weight capacity.The second phase takes into account the multiple types of available bins. If necessary, thebest found loading pattern is finally enhanced with respect to weight distribution in a postprocessing. After parametrisation, computational experiments have been performed on datasets especially designed for this application. The heuristic requires really short computationaltimes to achieve promising results.